MOOC算法学习笔记 - 动态规划（3）

例题一 help 小老鼠

例题二 滑雪

思路：
是一道很典型的动态规划的题
需要注意的是在递归的前提下如何记忆每次结果的

【总结】其实此题为多组动态规划 并取 最优解的问题

#include <iostream>  
using namespace std;  

int a[100][100];  
int b[100][100];  

int line,row;  

int skating(int i,int j)  
{  
   if(b[i][j]!=-1)              //首先判断有没有被算过
       return b[i][j];  
   int max=0;  
   if(i>0 && a[i][j]>a[i-1][j] && max<skating(i-1,j))      //这步集成了很多东西 十分精简   学习一下当遇到很多条件重合时 如何通过 if 解决
       max=skating(i-1,j);  
   if(i<line-1&&a[i][j]>a[i+1][j]&&max<skating(i+1,j))  
       max=skating(i+1,j);
   if(j>0&&a[i][j]>a[i][j-1]&&max<skating(i,j-1))  
       max=skating(i,j-1);  
   if(j<row-1&&a[i][j]>a[i][j+1]&&max<skating(i,j+1))  
       max=skating(i,j+1);  

   b[i][j]=max+1;         //自己做得时候就忽略这一步了！！！！
   return b[i][j];  
}  

int main()  
{  
    cin>>line>>row;  
    for(int i=0;i<line;i++)  
       for(int j=0;j<row;j++)  
           cin>>a[i][j];  
    for(int i=0;i<line;i++)  
       for(int j=0;j<row;j++)  
           b[i][j]=-1;  
    for(int i=0;i<line;i++)  
       for(int j=0;j<row;j++)  
       {  
           b[i][j]=skating(i,j);          //计算每个点的值
       }  
    int max=0;  
    for(int i=0;i<line;i++)          //对每个点遍历 找出最大值。
       for(int j=0;j<row;j++)  
          if(max<b[i][j]) max=b[i][j];  
    cout<<max<<endl;  
}

例题三

递归型代码

#include<iostream>
using namespace std;
int a[1000];
int N;
int Way(int w,int k){
    if( k<=0 )            //仔细想想边界条件 大多是0 或 1 分不清
        return 0;            
    if(w==0)
        return 1;
    return Way(w, k-1) + Way(w- a[k],k-1);    //由递归分部的思路得到
}
int main()
{
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> a[i];
    cout << Way(40, N) << endl;
    return 0;
}

递推型代码
要尤其注意各个for循环中的初值！！！！！！

#include <iostream>
#include<cstring>
using namespace std;
int main()
{
    int a[30],way[40][30];
    int N;
    cin >> N;
    memset(way,0,sizeof(way));  //csring中的函数
    for(int i = 1; i <= N; i++){    //递推中对初始条件进行初始化 才能推出后面的
        cin >> a[i];
        way[0][i] = 1;
    }
    way[0][0] =1;
    for(int w = 1; w < 40; w++)
        for(int k = 1; k < N; k++){
            way[w][k] = way[w][k-1];    //巧妙 完美解决了特殊情况
            if(w - a[k] >=0)
                way[w][k] = way[w-a[k]][k-1];        //可以参考递归的思路写出此步递推式
        }
    cout << way[40][N] <<endl;
    return 0;
}

例题四：背包问题

思路：
1.分解问题 找状态
显然是存放物品的，即N件物品一件一件的存放，状态就是对第 i 件物品放还是不放
待求价值总和 故设 F 为价值 又价值由 物品和体积所影响 故设F[i][j]
i表第几件物品，j 表剩余容积。
2.找边界条件/初始条件
当只剩一件物品的时候，
if w[1] >= j —–> F[1][j]=0
if w[1] < j ——-> F[1][j]+=d[1]
3.状态转移方程
F[i][j] = max{ F[i-1][j] , F[i-1][ j - w[i] ] + d[i]}

背包问题
参考三种基本类型的c++实现
参考背包九讲
(http://blog.csdn.net/stack_queue/article/details/53544109)